package com.zjj.algorithm.learning.leetcode.array;

import java.util.Arrays;

/**
 * 169. 多数元素 简单题
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,2,3]
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 *
 * @author zjj_admin
 * @date 2022/11/24 16:22
 */
public class MajorityElement {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 2, 1, 1, 1, 1, 1, 2, 2};
        int res = majorityElement2(arr);
        System.out.println("res = " + res);

    }


    /**
     * 此方法可以获取数组中元素最多的数据，当最多的数据没有超过总数的一半也可以
     * 时间
     * 3 ms
     * 击败
     * 35.55%
     * 内存
     * 44.9 MB
     * 击败
     * 64.47%
     *
     * @param nums
     * @return
     */
    public static int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        int maxNum = 1;
        int max = nums[0];
        int currNum = 1;
        int curr = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (curr == nums[i]) {
                currNum++;
                if (curr == max) {
                    maxNum++;
                } else {
                    if (currNum > maxNum) {
                        max = curr;
                        maxNum = curr;
                    }
                }
            } else {
                curr = nums[i];
                currNum = 1;
            }
        }
        return max;
    }


    /**
     * 时间
     * 2 ms
     * 击败
     * 61%
     * 内存
     * 45.2 MB
     * 击败
     * 35.48%
     *
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {
        // 将nums排序，则下标为n/2的元素一定是众数
        // 内置排序的时间复杂度O(nlogn),空间复杂度为O(logn),自己手写一个堆排序空间复杂度为O(1)
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

}
